#include "string_array.h"
#include <cstring>
using namespace std;


myStr::myStr() {
    data = nullptr;
    length = 0;
    next = nullptr;
    nextVal = nullptr;
}

myStr::myStr(const char* s) {
    length = strlen(s);
    data = new char[length + 1];
    for (int i = 0; i < length; i++)
        data[i] = s[i];
    data[length] = '\0';   

    next = nullptr;
    nextVal = nullptr;
}


myStr::myStr(const myStr& other) {
    length = other.length;
    data = new char[length];
    for (int i = 0; i < length; i++)
        data[i] = other.data[i];
    next = nullptr;
    nextVal = nullptr;
}

myStr::~myStr() {
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

void myStr::print() {
    for (int i = 0; i < length; i++)
        cout << data[i];
    cout << endl;
}

void myStr::printNext() {
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal() {
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}


void myStr::kmp_next() {
    if (next) delete[] next;
    next = new int[length];

    next[0] = 0;
    int j = 0;

    for (int i = 1; i < length; i++) {
        while (j > 0 && data[i] != data[j])
            j = next[j - 1];

        if (data[i] == data[j])
            j++;

        next[i] = j;
    }
}


void myStr::kmp_nextVal() {
    if (!next) kmp_next();

    if (nextVal) delete[] nextVal;
    nextVal = new int[length];

    nextVal[0] = 0;

    for (int i = 1; i < length; i++) {
        if (data[i] == data[next[i]])
            nextVal[i] = nextVal[next[i]];
        else
            nextVal[i] = next[i];
    }
}


int simpleMatch(const myStr& S, const myStr& T) {
    for (int i = 0; i <= S.length - T.length; i++) {
        int j = 0;
        while (j < T.length && S.data[i + j] == T.data[j]) j++;
        if (j == T.length) return i + 1;
    }
    return -1;
}


int kmpMatch(const myStr& S, const myStr& T) {
    if (!T.nextVal) ((myStr&)T).kmp_nextVal();

    int i = 0, j = 0;
    while (i < S.length && j < T.length) {
        if (S.data[i] == T.data[j]) {
            i++; j++;
        }
        else if (j == 0) {
            i++;
        }
        else {
            j = T.nextVal[j];
        }
    }

    if (j == T.length) return i - T.length + 1;
    return -1;
}


bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int pos = simpleMatch(S, T);
    if (pos == -1 || pos < start) return 0;

    int newLen = S.length - T.length + V.length;
    char* newData = new char[newLen];

    int k = 0;

    for (int i = 0; i < pos - 1; i++)
        newData[k++] = S.data[i];

    for (int i = 0; i < V.length; i++)
        newData[k++] = V.data[i];

    for (int i = pos - 1 + T.length; i < S.length; i++)
        newData[k++] = S.data[i];

    delete[] S.data;
    S.data = newData;
    S.length = newLen;

    delete[] S.next;
    delete[] S.nextVal;
    S.next = nullptr;
    S.nextVal = nullptr;

    return 1;
}



myMatrix::myMatrix() {
    rowNum = colNum = nodeNum = 0;
    nodeList = nullptr;
}

myMatrix::myMatrix(const int& r, const int& c, const int& n, const int* arr) {
    rowNum = r;
    colNum = c;
    nodeNum = n;
    nodeList = new matrixNode[n];

    for (int i = 0; i < n; i++) {
        nodeList[i].row = arr[i * 3];
        nodeList[i].col = arr[i * 3 + 1];
        nodeList[i].value = arr[i * 3 + 2];
    }
}

myMatrix::myMatrix(const myMatrix& other) {
    rowNum = other.rowNum;
    colNum = other.colNum;
    nodeNum = other.nodeNum;
    nodeList = new matrixNode[nodeNum];
    for (int i = 0; i < nodeNum; i++)
        nodeList[i] = other.nodeList[i];
}

myMatrix::~myMatrix() {
    delete[] nodeList;
}

void myMatrix::printMatrix() {
    cout << rowNum << "," << colNum << "," << nodeNum << endl;
    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}


void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    int* num = new int[colNum];
    int* cpot = new int[colNum];

    for (int i = 0; i < colNum; i++) num[i] = 0;

    for (int i = 0; i < nodeNum; i++)
        num[nodeList[i].col]++;

    cpot[0] = 0;
    for (int i = 1; i < colNum; i++)
        cpot[i] = cpot[i - 1] + num[i - 1];

    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;

    delete[] T.nodeList;
    T.nodeList = new matrixNode[nodeNum];

    for (int i = 0; i < nodeNum; i++) {
        int col = nodeList[i].col;
        int pos = cpot[col]++;

        T.nodeList[pos].row = nodeList[i].col;
        T.nodeList[pos].col = nodeList[i].row;
        T.nodeList[pos].value = nodeList[i].value;
    }

    delete[] num;
    delete[] cpot;
}

